# 《最长公共前缀》

# 编写一个函数来查找字符串数组中的最长公共前缀。
# 如果不存在公共前缀，返回空字符串 ""。

# 示例 1：
# 输入：strs = ["flower", "flow", "flight"]
# 输出："fl"

# 示例 2：
# 输入：strs = ["dog", "racecar", "car"]
# 输出：""
# 解释：输入不存在公共前缀。

# 提示：
# 1 <= strs.length <= 200
# 0 <= strs[i].length <= 200
# strs[i] 仅由小写英文字母组成
# 纵向、横向、分治、二分

# 纵向扫描
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        length = len(strs)
        prefix = []
        min = len(strs[0])
        # 获取最短字符串长度，防止索引越界
        for i in range(1, length):
            strlen = len(strs[i])
            if min > strlen: min = strlen
        # 以最短字符串长度为基准确定循环比较次数
        for i in range(min):
            flag = True
            # 比较不同字符串的同列字符是否相等
            for j in range(1,length):
                if strs[0][i] != strs[j][i]:
                    flag = False
                    break
            if flag == True:
                prefix += strs[0][i]
            else: break
        return ''.join(prefix)
    
# 示例代码：
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        pre = ''
        if not strs:
            return pre
        lens = [len(s) for s in strs]
        m_len = min(lens)
        for i in range(m_len):
            c = strs[0][i]
            f = True
            for s in strs[1:]:
                if s[i] != c:
                    f = False
                    break
            if f:
                pre += c
            else:
                break
        return pre
